package com.leetcode.partition3;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/7 21:56
 */
public class LC204计数质数 {

    public static int countPrimes(int n) {
        //线性筛
        boolean[] isNotPrimes = new boolean[n--];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (!isNotPrimes[i]) primes.add(i);
            for (int j = 0; primes.get(j) <= n / i; j++) {
                isNotPrimes[primes.get(j) * i] = true;
                if (i % primes.get(j) == 0) break;
            }
        }
        return primes.size();
    }
}
